6、岛屿个数
题目 岛屿个数
思路分析
先染色法 把外海标记出来
再用洪水灌溉 找岛屿数 如果岛屿能连接到外海 就是岛屿计数++ 如果连不到外海 就说明是岛中岛 不计数
结合了填涂颜色 山峰山谷几道题…蓝桥杯这样玩呢
这题确实不错 写得出说明前面染色法和洪水填充都学会了
找陆地部分bfs dfs都可以实现
和历届的一道全球变暖也有点像 升级版
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=55;
int g[N][N];
bool st[N][N];
int n,m;
bool isVaild(int x,int y){
return x>=0 && x<=n+1 && y>=0 && y<=m+1;
}
//八连通找外海
int dx_h[8]={-1,-1,0,1,1,1,0,-1};
int dy_h[8]={0,1,1,1,0,-1,-1,-1};
void bfs(int x,int y){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(q.size()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
g[ux][uy]=2;
for(int i=0;i<8;i++){
int nx=ux+dx_h[i],ny=uy+dy_h[i];
if(isVaild(nx,ny) && g[nx][ny]==0 && !st[nx][ny]){
st[nx][ny]=true;
q.push({nx,ny});
}
}
}
}
//四连通找陆地
int dx_l[4]={-1,0,1,0};
int dy_l[4]={0,1,0,-1};
void dfs(int x,int y,bool &island){
for(int i=0;i<4;i++){
int nx=x+dx_l[i],ny=y+dy_l[i];
if(isVaild(nx,ny)){
if(g[nx][ny]==2){
island=true;
}
if(g[nx][ny]==1 && !st[nx][ny]){
st[nx][ny]=true;
dfs(nx,ny,island);
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n>>m;
memset(g,0,sizeof g);
memset(st,false,sizeof st);
for(int i=1;i<=n;i++){
string s;cin>>s;
for(int j=1;j<=m;j++){
g[i][j]=s[j-1]-'0';
}
}//数据在1~n 1~m 外圈加了一圈0 范围0~n+1 0~m+1
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++){
// cout<<g[i][j]<<" ";
// }
// cout<<endl;
// }
bfs(0,0);//染色法 标记外海
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++){
// cout<<g[i][j]<<" ";
// }
// cout<<endl;
// }
//洪水灌溉找连通块 且有外海相邻
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]==1 && !st[i][j]){
bool island=false;
st[i][j]=true;
dfs(i,j,island);
if(island){
cnt++;
}
}
}
}
cout<<cnt<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=55;
int g[N][N];
bool st[N][N];
int n,m;
bool isVaild(int x,int y){
return x>=0 && x<=n+1 && y>=0 && y<=m+1;
}
int dx_h[8]={-1,-1,0,1,1,1,0,-1};
int dy_h[8]={0,1,1,1,0,-1,-1,-1};
void bfs1(int x,int y){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(q.size()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
g[ux][uy]=2;
for(int i=0;i<8;i++){
int nx=ux+dx_h[i],ny=uy+dy_h[i];
if(isVaild(nx,ny) && g[nx][ny]==0 && !st[nx][ny]){
st[nx][ny]=true;
q.push({nx,ny});
}
}
}
}
int dx_l[4]={-1,0,1,0};
int dy_l[4]={0,1,0,-1};
void bfs2(int x,int y,bool &island){
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first,uy=cur.second;
for(int i=0;i<4;i++){
int nx=ux+dx_l[i],ny=uy+dy_l[i];
if(isVaild(nx,ny)){
if(g[nx][ny]==2){
island=true;
}
if(g[nx][ny]==1 && !st[nx][ny]){
st[nx][ny]=true;
q.push({nx,ny});
}
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n>>m;
memset(g,0,sizeof g);
memset(st,false,sizeof st);
for(int i=1;i<=n;i++){
string s;cin>>s;
for(int j=1;j<=m;j++){
g[i][j]=s[j-1]-'0';
}
}//数据在1~n 1~m 外圈加了一圈0 范围0~n+1 0~m+1
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++){
// cout<<g[i][j]<<" ";
// }
// cout<<endl;
// }
bfs1(0,0);//染色法 标记外海 为2
// for(int i=0;i<=n+1;i++){
// for(int j=0;j<=m+1;j++){
// cout<<g[i][j]<<" ";
// }
// cout<<endl;
// }
//洪水灌溉找连通块 且有外海相邻
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]==1 && !st[i][j]){
bool island=false;
bfs2(i,j,island);
if(island){
cnt++;
}
}
}
}
cout<<cnt<<endl;
}
return 0;
}
💬 评论